package org.example.SolutionNew002;

import java.util.Stack;

public class LinkedList08 {
    public static void main(String[] args) {
        LinkedList08 l = new LinkedList08();
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        ListNode res=l.removeNthFromEnd(head1, 1);
        while(res!=null){
            System.out.println(res.val);
            res=res.next;
        }
    }

    //双指针
    public ListNode removeNthFromEnd0(ListNode head, int n) {
        ListNode prev=head;
        ListNode tail=prev;
        for(int i=0;i<n;i++){
            tail=tail.next;
        }
        if(tail==null) return prev.next;
        while(tail.next!=null){
            prev=prev.next;
            tail=tail.next;
        }
        ListNode tmp=prev.next;
        prev.next=tmp.next;
        return head;
    }

    //栈
    public ListNode removeNthFromEnd(ListNode head, int n) {
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode temp=head;
        while(temp!=null){
            stack.push(temp);
            temp=temp.next;
        }
        for(int i=0;i<n;i++){
            temp=stack.pop();
        }
        if(stack.isEmpty()) return head.next;
        ListNode prev=stack.peek();
        prev.next = temp.next;
        return head;
    }
}
